#leetcode题目483：找到字符串中所有字母异位词
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：滑动窗口

#解法来自leetcode官方题解

from typing import List
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)
        
        if s_len < p_len:
            return []

        ans = []
        s_count = [0] * 26
        p_count = [0] * 26
        for i in range(p_len):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1

        if s_count == p_count:
            ans.append(0)

        for i in range(s_len - p_len):
            s_count[ord(s[i]) - 97] -= 1
            s_count[ord(s[i + p_len]) - 97] += 1
            
            if s_count == p_count:
                ans.append(i + 1)

        return ans

        ###解法来自第三个视频，由java转成python而来。
        #TODO
        




#测试数据

S = "cbaebabacd"
P = "abc"
#预期输出：[0,6]

solution = Solution()
print(solution.findAnagrams(S, P))

S = "abab"
P = "ab"
#预期输出：[0,1,2]

solution = Solution()
print(solution.findAnagrams(S, P))



